-------<br />METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France)<br />-------<br />Workshop on Metric embeddings, algorithms and hardness of approximation<br />January 17-21, 2011<br />-------<br />Jan 17, 13:30-14:30<br />Moses Charikar (Princeton U.)<br />A Near Linear Lower Bound for Dimension Reduction in L1<br />-------<br />Given a set of n points in L1, how many dimensions are needed to<br />represent all pairwise distances within a specific distortion ? This<br />dimension-distortion tradeoff question is well understood for the L2<br />norm, where O(log n)/eps2) dimensions suffice to achieve 1+eps<br />distortion. In sharp contrast, there is a significant gap between<br />upper and lower bounds for dimension reduction in L1. In this work,<br />we show the first near linear lower bounds for dimension reduction in<br />L1. In particular, we show that 1+eps distortion requires at least<br />n^{1-O(1/log(1/eps))} dimensions.<br /><br />Our proofs are combinatorial, but inspired by linear programming. In<br />fact, our techniques lead to a simple combinatorial argument that is<br />equivalent to the LP based proof of Brinkman-Charikar for lower bounds<br />on dimension reduction in L1.<br /><br />Joint work with Alex Andoni, Ofer Neiman and Huy Nguyen.
